﻿using System;
using System.Collections.Generic;
using System.Diagnostics;


 public class TreeNode
{
     public int val;
     public TreeNode left;
     public TreeNode right;
     public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
  {
     this.val = val;
     this.left = left;
     this.right = right;
          }
 }

public class Solution103
{
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root)
    {

        
        LinkedList<TreeNode> deque = new LinkedList<TreeNode>();
        IList<IList<int>> res = new List<IList<int>>();
        bool flag = false;
        if (root == null)
        {
            return res;
        }
        deque.AddFirst(root);
        while (deque.Count > 0)
        {
            //不在入队的时候收集，也不在出队的时候收集

            int curLen = deque.Count;
            IList<int> list = new List<int>();

            
                TreeNode cur =new TreeNode();
                //无论从后往前，还是从前往后，队伍里面必须是层级遍历的顺序
                if (flag)
                {
                    flag = !flag;
                for (int i = 0; i < curLen; i++)
                {
                    cur = deque.Last();
                    deque.RemoveLast();

                    list.Add(cur.val);

                    if (cur.right != null)
                    {
                        deque.AddFirst(cur.right);
                    }
                    if (cur.left != null)
                    {
                        deque.AddFirst(cur.left);
                    }
                }
                }
                else
                {
                    flag = !flag;
                for (int i = 0; i < curLen; i++)
                {
                    cur = deque.First();
                    deque.RemoveFirst();

                    list.Add(cur.val);

                    if (cur.left != null)
                    {
                        deque.AddLast(cur.left);
                    }
                    if (cur.right != null)
                    {
                        deque.AddLast(cur.right);
                    }
                }
                }
               


            
            res.Add(list);


        }

        return res;
    }
}
